MÓNADAS

La generalización de las continuaciones
“La mónada no es sino una sustancia simple que entra en entidades compuestas; simple, es decir, sin partes” (Leibniz. Monadología)

---

Mónada en teoría de categorías

El concepto de mónada (en inglés, monad) pertenece a la teoría de categorías.

Una categoría está formada por una clase (un conjunto de objetos) y un conjunto de morfismos. Un morfismo (o flecha) es una relación dirigida entre dos objetos A y B de la clase (una relación binaria), que se expresa como A→B.

Una categoría C cumple los dos axiomas siguientes:

1. Composición asociativa de morfismos:
   h ο (g ο f) = (h ο g) ο f
   
   
2. Morfismo identidad. Para todo objeto x de C existe un morfismo identidad 1_x que le hace corresponder a sí mismo.

Un funtor (o functor) es una función de una categoría a otra que lleva objetos a objetos y morfismos a morfismos de manera que la composición de morfismos y las identidades se preservan. Un endofunctor es un funtor de una categoría sobre sí misma.

Una transformación natural transforma un funtor en otro respetando su estructura interna, es decir la composición de morfismos, de las categorías implicadas. Se puede considerar como un morfismo de funtores.

Una vez revisados estos conceptos de la teoría de categorías, podemos dar la definición formal de mónada sobre una categoría C, también llamada “triple” porque se define mediante tres axiomas:

• Un endofuntor T. T: C → C
  
  
• Dos transformaciones naturales:
  
  η: 1_T → T (transformación natural del morfismo identidad de T en T)
  
  μ: T² → T (T² indica aplicar T dos veces).

Podemos considerar una mónada como una categoría en la que los objetos son estados de un sistema y los morfismos son funciones de transición entre estados.


Mónadas en lenguajes de programación funcionales

Como el concepto clave de la teoría de categorías es el de morfismo, las mónadas se están aplicando en los lenguajes de programación funcionales. Estos lenguajes son de dos tipos:

• Los “puros”, que son los que utilizan exclusivamente funciones, con transparencia referencial (la propiedad de obtener siempre los mismos resultados con los mismos valores de entrada y sin efectos colaterales). Las ventajas de los lenguajes funcionales puros son: son más fáciles de entender (el flujo de datos es explícito) y pueden tener evaluación perezosa (lazy). Las desventajas es que el paradigma funcional muchas veces es insuficiente, pues necesita de otros paradigmas, principalmente el paradigma imperativo. Lenguajes funcionales puros son Haskell y Miranda.
  
  
• Los “impuros”, que son los que incluyen, además de funciones, recursos propios de un lenguaje imperativo. Las ventajas de los impuros son: mayor eficiencia y expresiones más compactas. Lenguajes funcionales impuros son Scheme y Standar ML.

La tendencia es integrar ambos aspectos en los lenguajes funcionales. Uno de los mecanismos utilizados para este fin es precisamente el uso de mónadas. Las mónadas se utilizan como mecanismo complementario de los lenguajes funcionales puros para que soporten el paradigma imperativo. En programación funcional, una mónada es una estructura que representa una secuencia de transformaciones de un objeto. Para usar las mónadas en un lenguaje funcional no es necesario tener un conocimiento previo de la teoría de categorías.

La idea básica de una mónada en programación funcional es la siguiente:

Una función f es sustituida por otra más general m (la mónada), de tal manera que dentro de ella se invoca a la original (f) y se realiza un proceso adicional. El resultado de la función mónada (m) es el mismo que si se hubiera invocado directamente a f. Así, pues, una mónada es una función de orden superior que incluye a la función original y que realiza un proceso adicional de tipo imperativo.

La función mónada también se denomina “contenedor”, pues contiene a la función original.


Mónadas en Haskell

Haskell [Bird, 2000], uno de los lenguajes funcionales puros más conocidos, utiliza mónadas. En Haskell las tres funciones de las mónadas se reducen a dos: return y bind (ligar, unir). Esta última se representa como “>>=”.

En Haskell, por definición, M es una mónada cuando posee las dos operaciones siguientes:

1. return :: a → M a
   Esta operación admite varias interpretaciones:
   
   
   • Es un contenedor o mónada M que contiene el valor básico o tipo a.
     
     
   • El valor básico o tipo a es de tipo M.
     
     
   • El tipo monádico M a representa una computación que produce el valor básico o tipo a.
   
   Por ejemplo, en la interpretación del contenedor, si tengo una manzana (a), la puedo poner en una caja (M).
   
   
2. (>>=) :: M a → (a → M b) → M b
   Combina dos computaciones en secuencia, pasando el resultado de la primera como argumento de la segunda. Esta operación es asociativa.
   
   Se aplica la función (a → M b) con el valor de entrada (M a), cuyo resultado es M(M b)) que se junta para obtener un contenedor de tipo (M b).
   
   Por ejemplo, si tengo una caja de manzanas (M a), y si por cada manzanza obtengo una caja de peras, entonces puedo obtener una caja con todas las peras juntas.

Haskell también define la meta-función fmap, que aplica una función f a todos los elementos de un contenedor, de tal manera que los objetos a, b, c, … del contenedor se transforman en f(a), f(b), f(c), … y los morfismos de tipo a → b se transforman en f(a) → f(b). Se define así:

fmap :: (a → b) → (fa → fb)

Por ejemplo, si de cada manzana obtengo una pera (a → b), de una caja de manzanas obtengo una caja de peras (fa → fb).

La función fmap es un caso particular del denominado “lifting monádico”, donde se sustituyen valores básicos por valores monádicos, es decir, generaliza una función sustituyendo los argumentos por contenedores. En general,

f(T₁ … T_n) → r ⇒ f(MT₁ … MT_n) → Mr

Las mónadas transformaron Haskell convirtiéndolo en un lenguaje de programación imperativo. Haskell popularizó el uso de mónadas para la programación imperativa con la notación do.


Mónadas vs. Continuaciones

Una continuación se puede expresar así: f(x, c) = c(f(x)), es decir, la continuación c es una función que es un parámetro de otra función. Por ejemplo,

cuadrado(x, c) = c(x*x)
sumar5(x) = x+5
cuadrado(x, sumar5) = sumar5(x*x)

Existe una estrecha relación entre mónadas y continuaciones. En ambos casos hay que especificar una función adicional:

• En el caso de las mónadas, dicha función adicional se especifica fuera del entorno del flujo de ejecución del programa.
  
  
• En el caso de las continuaciones, se especifica dentro del programa principal.

Si se utilizan mónadas, la especificación de continuaciones se hace más simple, más claro y más fácil de actualizar, pues no hay que modificar todo el programa, solo hay que redefinir las mónadas.

Eugenio Moggi [1989] ha demostrado que el concepto de mónada es más general que el de continuación. Dicho de otra forma, una continuación es un caso particular de mónada. La composición de continuaciones tiene estructura monádica.


Mónadas, álgebra abstracta y álgebra universal

Una mónada es esencialmente un monoide en una categoría endofuntora. En álgebra abstracta, un monoide es una estructura algebraica con una operación binaria interna, que es asociativa y que tiene un elemento neutro. Es decir, una mónada es un semigrupo con elemento neutro. Un semigrupo es un conjunto con una operación interna asociativa.

El álgebra universal es una generalización del álgebra abstracta que estudia las propiedades comunes y genéricas de todas las operaciones y estructuras algebraicas sobre un conjunto. Es una especie de meta-teoría algebraica basada en un pequeño número de axiomas.

La teoría de categorías y el álgebra universal tienen como objetivo la fundamentación de todas las estructuras algebraicas. El álgebra universal se basa en las operaciones internas que definen la estructura. La teoría de categorías se basa en morfismos.

El álgebra universal se puede formular en términos de la teoría de categorías, en particular se puede definir en términos de mónadas. Por lo tanto, con las mónadas se puede construir toda estructura algebraica. Existe una equivalencia entre el álgebra universal y las mónadas en la categoría Sets (la categoría de los conjuntos). Las mónadas permiten expresar de forma compacta ciertos aspectos del álgebra universal.

Las mónadas suministran una visión diferente del álgebra universal. Por ejemplo, las variedades se pueden representar con mónadas. El álgebra universal es esencialmente el estudio de las variedades. Una variedad es una generalización de curva (1-variedad) y superficie (2-variedad) a n dimensiones.


Ventajas y limitaciones de las mónadas en los lenguajes funcionales puros

Las ventajas son:

• Suplementan las carencias de los lenguajes funcionales puros. La programación monádica permite escribir programas funcionales que se asemejan a programas imperativos. Muchos conceptos de programación imperativa se definen de manera puramente funcional, sin necesidad de extender la semántica del lenguaje.
  
  
• Separan claramente los componentes imperativo y funcional de un programa.
  
  
• Proporcionan modularidad. Cada mónada es un módulo.
  
  
• Permiten crear lenguajes embebidos en el lenguaje funcional o crear lenguajes específicos de dominio.
  
  
• Implementan acciones de interacción con el entorno y permiten abordar una serie de problemas específicos sin necesidad de modificar apenas el programa que implementa la funcionalidad.
  
  
• Aportan flexibilidad. Los programas funcionales con mónadas son más adaptables, pues los cambios son más fáciles, al realizarse básicamente en un solo lugar (en la definición de las mónadas), en lugar de realizarlos a lo largo de todo el programa fuente. Las funciones se componen de manera diferente según la mónada que se utilice.
  
  
• Se logra mejorar la legibilidad del programa y se simplifica la programación, liberando al programador de incluir el mismo código en cada punto del programa que se necesite.
  
  
• Con las mónadas el programador no necesita explicitar los tipos de parámetros que requiere cada función. La función bind es la encargada del paso de parámetros. Usando mónadas, el código fuente se parece más a una cadena de nombres de función, sin mecanismos explícitos de llamadas de una función a otra. Las mónadas difuminan la distinción entre objetos y morfismos.
  
  
• Las mónadas favorecen la utilización de combinadores (combinators) en la programación funcional. Un combinador es una función que construye un fragmento de código fuente a partir de otros fragmentos de código fuente. La programación funcional utiliza en gran medida los combinadores para construir programas. Con los combinadores la programación se hace más sencilla y potente porque son mecanismos de alto nivel que permiten prescindir de los detalles (de bajo nivel).
  
  Ejemplos de combinadores genéricos son fmap (aplicar una función a los elementos de una lista) y filter (seleccionar los elementos de una lista que cumplen una condición). Un ejemplo de combinador específico es parsing (análisis sintáctico).

Y las limitaciones son importantes:

• Son poco intuitivas, difíciles de entender y usar, debido a su naturaleza abstracta.
  
  
• Es un mecanismo no suficientemente genérico. Solo se aplican en lenguajes funcionales y mediante funciones.
  
  
• Rompen la elegancia de los programas funcionales puros. Hay dos estilos de programación: el estilo de programación funcional y el estilo de programación monádico. Aunque en ejecución hay, evidentemente, conexión entre ambos, en la codificación están separados.
  
  
• Tienen limitaciones combinatorias y es complejo crear mónadas de orden superior. No existe una técnica general para combinar mónadas. Para facilitar la combinatoria de mónadas se utilizan unas mónadas especiales llamadas “transformadores de mónadas”.
  
  Un transformador de mónada [King y Wadler, 1992] es una mónada parametrizada sobre otra mónada, de tal forma que las computaciones sobre la segunda mónada pueden ser elevadas a computaciones sobre la primera (la nueva mónada). Combinando varios transformadores de mónadas, se pueden construir una gran variedad de mónadas de orden superior.

Implementación de Mónadas en MENTAL
Teoría de categorías vs. MENTAL

La teoría de categorías es una teoría con un fundamento simple (relaciones binarias entre objetos). Pero paradójicamente es una teoría compleja, antinatural, demasiado abstracta y poco intuitiva por dos razones: 1) por fundamentarse en una sola primitiva conceptual (el morfismo); 2) porque esta primitiva es ambigua, no tiene semántica definida, es abierta, pues el concepto de morfismo admite muchas interpretaciones.

Además, la teoría de categorías es poco adecuada para fundamentar la matemática y poco adecuada para aplicarla a la programación. Las verdaderas categorías son las primitivas semánticas universales, que establecen los grados de libertad. [ver Aplicaciones – Matemática – Teoría de Categorías].


Mónadas vs. expresiones genéricas

El concepto de mónada es tan confuso que se ha intentado definir de muchas formas, entre ellas las siguientes:

• Una sobrecarga (overload) de las operaciones, es decir, la asignación de nuevas semánticas a las operaciones.
  
  
• Un patrón o interfaz estándarizado para combinar funciones.
  
  
• Una forma de componer funciones pero con condiciones.
  
  
• Un contenedor.
  
  
• Un endofuntor que actúa sobre los objetos y morfismos de un contenedor.
  
  
• Un patrón computacional.
  
  
• Un patrón de diseño que permite modelas efectos colaterales en la programación funcional.
  
  
• Una función de orden superior o una forma de generalizar funciones.
  
  
• Una especie de cinta transportadora o de cadena de ensamblaje. Un objeto es sometido a una serie de transformaciones, en donde el resultado de cada paso es la entrada al siguiente.

Incluso se ha afirmado que el concepto de mónada es inefable, que no es posible definirlo y que solo podemos usarlo en aplicaciones concretas.

La definición que parece que quizás más se aproxima al concepto es la siguiente: una mónada es un patrón de diseño para componer funciones con tipos extendidos. Un tipo extendido es un tipo más general que incluye al tipo básico.

Sin embargo, esta definición no es suficientemente clara. Las mónadas son realmente expresiones genéricas disfrazadas. Con las expresiones genéricas de MENTAL los mecanismos de las mónadas se simplifican y aclaran. Además, se superan sus limitaciones.

• Las mónadas de los lenguajes funcionales se sitúan en un nivel “meta” y afectan de manera global al programa en algunos aspectos computacionales de un programa funcional puro. En este sentido existe una analogía con la programación orientada a aspectos o a eventos.
  
  
• Las expresiones genéricas (parametrizadas o no) permiten expresar lo que realizan las mónadas. Pueden utilizar todos los recursos del lenguaje, de manera verdaderamente genérica y de forma más simple y más modular. Además no se necesita modificar el programa fuente.
  
  En MENTAL las expresiones genéricas no están ligadas a las funciones, sino a todas las expresiones del lenguaje. Las funcionalidades de las mónadas se pueden expresar de manera más simple y directa con MENTAL.
  
  
• Las mónadas no pueden combinarse de forma general. Para combinar una mónada con otra hay que definir un transformador de mónada que convierte una mónada en otra. En MENTAL, las primitivas se combinan libremente.
  
  
• Con MENTAL se puede aplicar cualquier paradigma de programación, no solo al paradigma funcional. El futuro de la programación no pasa por las mónadas sino por el nivel de abstracción supremo. Además, MENTAL es un paradigma universal, y no solo en programación. El nivel de abstracción de MENTAL es supremo, por lo que permite expresar la teoría de categorías, las mónadas, el álgebra abstracta y el álgebra universal. Fundamenta a todas las ciencias formales.
  
  
• La operación bind de las mónadas se puede expresar así en MENTAL:
  
  ⟨( M=a → a=(M=b) → M=b )⟩
  
  Si una computación M produce a (o una expresión M se evalúa como a) y si a produce una computación que produce b, entonces la computación M produce b.

Ejemplos

En el tema de la relación entre objetos y tranformaciones, existen dos procesos extremos:

1. Una misma función se aplica sucesivamente a varios objetos de una secuencia. Corresponde a la meta-función fmap de algunos lenguajes de programación funcional como Haskell y Lisp. Se trata de una función de orden superior que aplica la función inicial a cada elemento de una lista, retornando una lista de resultados en el mismo orden.
   
   
2. Un mismo objeto es sometido a varias transformaciones sucesivas.

En la práctica, estos dos tipos de procesos pueden llegar a confundirse, pues una secuencia de objetos se puede considerar un solo objeto.

Estos dos procesos se pueden especificar de una manera extremadamente simple en MENTAL.

En el primer caso, la meta-función fmap se expresa así:

⟨( (fmap f x) = ( [f([x↓])] ) )⟩
(f se aplica a cada uno de los componentes de x)

Ejemplos:

1. ⟨( f(x) = x*x )⟩)
(a = (1 2 3 4))
(fmap f a) // ev. (1 4 9 16)
   
   
2. ⟨( f(x) = (x x+10)↓ )⟩
(a = (1 2 3 4))
(fmap f a) // ev. (1 11 2 12 3 13 4 14)
   
   
3. Queremos someter una secuencia numérica a una transformación tal que cada elemento de la secuencia se transforme en dos secuencias:
   
   
   f: n → (n, n), (n+1, n+2)
   
   Por ejemplo, si tenemos el objeto (1, 2, 3, 4), el resultado es
   
   
   (1,1), (2,3), (2,2), (3,4), (3,3), (4,5), (4,4), (5,6)
   
   En MENTAL:
   
   
   ⟨( f(n) = ((n n) (n+1 n+2))↓ )⟩
   
   Esta función convierte un número en una expresión abierta formada por dos secuencias.
   
   
   (x = (1 2 3 4))
(fmap f x) // ev.
((1 1) (2 3) (2 2) (3 4) (3 3) (4 5) (4 4) (5 6))

En el segundo caso tenemos, por ejemplo, las funciones:

⟨( f1(n) = 2*n )⟩
⟨( f2(n) = n*n )⟩
⟨( f3(n) = n+100 )⟩ ⟨( T(n) = f3(f2(f1(n))) )⟩
T(5) // ev. 200

En este ejemplo, las funciones se pueden encadenar sin problemas. Pero hay veces que el encadenamiento no puede realizarse de forma mecánica cuando hay errores, por ejemplo, al tratar de calcular la raíz cuadrada de un número negativo. Por ejemplo:

Definimos ⟨( fοg = g(f) )⟩ (composición de funciones)
con la propiedad asociativa:
⟨( (fοg)οh ≡ fο(gοh) )⟩.

Por ejemplo,
(sqrt(r) ο sumar5(r))
se evalúa como (sumar5(sqrt(r))),
siendo ⟨( sumar5(r) = r+5 )⟩.

Suponemos que la función sqrt(r) devuelve la raíz cuadrada de r si es r>0 o el texto “error” si r<0. La función siguiente debe chequear primero, antes de aplicarla, que el resultado de la función anterior es un número y no un mensaje de error. Si detecta el mensaje de error, su respuesta debe ser también el mismo mensaje de error. La nueva función sería:

(sumar5(r) ← r≥0 →' "error")

Este mismo mecanismo habría que aplicarlo a las posibles siguientes funciones de la cadena. Para no repetirlo, podemos crear una expresión genérica:

⟨( (M(f(r)) = (f(r) ← r≥0 →' "error") )⟩

Por lo tanto, la expresión de concatenación de las dos funciones sería:

(sqrt(r) ο M(sumar5(r)))

En este ejemplo se podrían especificar dos valores de salida (el resultado de la función y un mensaje que indique si ha habido error o no.

---

Adenda
Orígen de las mónadas

El término “mónada” está prestado de Leibniz, de la misma forma que el término “categoría” está prestado de Kant. Para Leibniz, una mónada es una sustancia simple que forma parte de todos los elementos de la realidad.

Saunders Mac Lane cofundador de la teoría de categorías, junto con Samuel Eilenberg adoptó el término filosófico de “mónada” para hacer referencia a algo general, una entidad capaz de generar todas las otras entidades. Pero eso no significa que la mónada sea simple, pues el concepto de mónada en teoría de categorías es muy abstracto, complejo y poco intuitivo, por lo que va en contra de la concepción de Leibniz. La popularidad del término ¨mónada” se debe probablemente al propio Mac Lane por su influyente libro Category Theory for the Working Mathematician. También se cree que el término “mónada” fue motivada y estimulada por su similitud con la palabra “monoide”, pues una mónada es un monoide.

Las mónadas han sido conocidas por otros nombres: triple o triada (por su definición mediante tres axiomas) y construcción estándar (por su pretensión de ser algo que fundamentase todo lo demás).

En álgebra abstracta, un monoide es una estructura algebraica con una sola operación binaria asociativa y un elemento identidad.

La primera mónada que se construyó fue presentada por Roger Godemont en 1958 [Barr & Wells, 1985].

Eugenio Moggi [1989, 1990, 2000] fue el primero en introducir las mónadas en computación, concretamente en el área de la semántica denotacional [Stoy, 1997] para intentar modelar su significado. La semántica denotacional se basa en asignar a cada elemento del lenguaje un objeto matemático.

Spivey [1990] descubrió que las mónadas proporcionaban una forma fácil de de tratar las excepciones.

Philip Wadler [1990, 1992, 1995, 1997] popularizó las ideas de Moggi al proponer las mónadas como una técnica general para extender los lenguajes funcionales a la programación imperativa.

Las mónadas se han utilizado en el desarrollo del compilador de Haskell de Glasgow (que está escrito en Haskell).


Aplicaciones de las mónadas

Las mónadas se están aplicando, en diversos campos:

• Tratamiento de excepciones y errores.
• Estados globales.
• Entrada/salida.
• Gestión de matrices (acceso, actualización in situ, etc.).
• Traceado de ejecución de programas.
• Gestión de estados internos y externos de un programa.
• Gestión de estructuras de datos.
• Gestión del orden de las operaciones (trazas de ejecución).
• Gestión de la memoria.
• Comunicación entre procesos concurrentes.
• Análisis sintáctico (parsing).
• Intérpretes y compiladores.
• Logging.
• Interfaz a código escrito en otros lenguajes.
• Continuaciones.
• Gestión de un interfaz gráfico de usuario (GUI).
• Metaprogramación.
• Programación no determinista.

Mónadas predefinidas en Haskell

Haskell suministra mónadas predefinidas para utilizarlas como funciones y para combinación de funciones.

Mónada	Descripción
Maybe	Computaciones que pueden retornar o no un resultado
Identity	Mónada identidad
[] (List)	Computaciones que retornan múltiples resultados
IO	Computaciones que realizan Entrada/Salida
Error	Computaciones que pueden fallar o producir excepciones
State	Computaciones que mantienen el estado
Reader	Computaciones que leen datos
Writer	Computaciones que escriben datos
Cont	Computaciones que pueden interrumpirse o reiniciarse

Bibliografía

• Barr, M.; Walls, C. Toposes, Triples and Theories. A series of Comprehensive Studies in Mathematics. Springer, 1985.
  
  
• Bird, Richard. Introducción a la Programación Funcional con Haskell. Prentice Hall, 2000.
  
  
• Internet. Monads in Haskell. http://www.haskell.org.
  
  
• King, David; Wadler, Phil. Combining Monads. In Glasgow Workshop on Functional Programming. Ayr, July 1992. Springer-Verlag.
  
  
• Mac Lane, Saunders. Category Theory for the Working Mathematician. Graduate Texts in Mathematics. Springer, 1978.
  
  
• Moggi, Eugenio. Computational lambda-calculus and monads. In IEEE Symposium on Logic in Computer Science. Asilomar, Calif. USA, 1989. Disponible online.
  
  
• Moggi, Eugenio. An abstract view of programming languages. Technical Report ECS-LFCS-90-113, Laboratory for Foundations of Computer Science, University of Edinbourgh, Scotland, 1990.
  
  
• Moggi, Eugenio. Notions of computation and monads. Information and Control, 93, 55-92, 2000.
  
  
• Newbern, Jeff. All about Monads. http://www.nomaware.com / monads.html. [Buenos ejemplo de mónadas, con explicaciones].
  
  
• Spivey, M. A functional theory of exceptions. Science of Computer Programming 14: 25-42, 1990.
  
  
• Stoy, Joseph. Denotational Semantics. The Scott-Stratchey Approach to Programming Laguages Theory. MIT Press, 1997.
  
  
• Wadler, Philip. Comprehending monads. In Conference on Lisp and Functional Programming, Nice, France. ACM, June 1990.
  
  
• Wadler, Philip. The essence of functional programming. In Conference Record of the Nineteenth Annual ACM Symposium on Principles of Programming Languages, Alburquerque, New Mexico, pp. 1-14, January 1992.
  
  
• Wadler, Philip. Monads for functional programming. Internet. Copia de artículo publicado en 1995. [Una buena intrducción].
  
  
• Wadler, Philip. How to Declare Imperative. ACM Computing Surveys, 29(3): 240-263, 1997.